|
Marzullo's algorithm, invented by Keith Marzullo for his Ph.D. dissertation in 1984, is an agreement algorithm used to select sources for estimating accurate time from a number of noisy time sources. A refined version of it, renamed the "intersection algorithm", forms part of the modern Network Time Protocol. The Marzullo's algorithm is also used to compute the relaxed intersection of n boxes (or more generally ''n'' subsets of R''n''), as required by several robust set estimation methods. ==Purpose== Marzullo's algorithm is efficient in terms of time for producing an optimal value from a set of estimates with confidence intervals where the actual value may be outside the confidence interval for some sources. In this case the best estimate is taken to be the smallest interval consistent with the largest number of sources. If we have the estimates 10 ± 2, 12 ± 1 and 11 ± 1 then these intervals are (), () and () which intersect to form () or 11.5 ± 0.5 as consistent with all three values. If instead the ranges are (), () and () then there is no interval consistent with all these values but () is consistent with the largest number of sources — namely, two of them. Finally, if the ranges are (), () and () then both the intervals () and () are consistent with the largest number of sources. This procedure determines an interval. If the desired result is a best value from that interval then a naive approach would be to take the center of the interval as the value, which is what was specified in the original Marzullo algorithm. A more sophisticated approach would recognize that this could be throwing away useful information from the confidence intervals of the sources and that a probabilistic model of the sources could return a value other than the center. Note that the computed value is probably better described as "optimistic" rather than "optimal". For example, consider three intervals (), (13 ) and (). The algorithm described below computes (12 ) or 11.995 ± 0.005 which is a very precise value. If we suspect that one of the estimates might be incorrect, then at least two of the estimates must be correct. Under this condition, the best estimate is () since this is the largest interval that always intersects at least two estimates. The algorithm described below is easily parameterized with the maximum number of incorrect estimates. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Marzullo's algorithm」の詳細全文を読む スポンサード リンク
|